/*
 * @lc app=leetcode.cn id=380 lang=javascript
 *
 * [380] O(1) 时间插入、删除和获取随机元素
 */

// @lc code=start

var RandomizedSet = function () {
  this.data = [];
  // 数组的 值 和 下标 映射关系
  this.map = new Map();
};

/**
 * @param {number} val
 * @return {boolean}
 */
RandomizedSet.prototype.insert = function (val) {
  if (this.map.has(val)) return false;
  this.data.push(val);
  this.map.set(val, this.data.length - 1);
  return true;
};

/**
 * @param {number} val
 * @return {boolean}
 */
RandomizedSet.prototype.remove = function (val) {
  if (!this.map.has(val)) return false;
  let index = this.map.get(val);
  if (index !== this.data.length - 1) {
    [this.data[index], this.data[this.data.length - 1]] = [
      this.data[this.data.length - 1],
      this.data[index],
    ];
  }
  this.data.pop();
  this.map.delete(val);
  this.map.set(this.data[index], index);
  return true;
};

/**
 * @return {number}
 */
RandomizedSet.prototype.getRandom = function () {
  return this.data[Math.floor(Math.random() * this.data.length)];
};

/**
 * Your RandomizedSet object will be instantiated and called as such:
 * var obj = new RandomizedSet()
 * var param_1 = obj.insert(val)
 * var param_2 = obj.remove(val)
 * var param_3 = obj.getRandom()
 */
// @lc code=end
